import java.util.ArrayList;
import java.util.List;

/**
 * 78. Subsets 子集
 * https://leetcode.com/problems/subsets/
 */
class Subsets {
    private final List<List<Integer>> ans = new ArrayList<>();
    private final List<Integer> path = new ArrayList<>();
    private int[] nums;

    /**
     * 方法：回溯算法，通过枚举选择元素来生成所有子集
     * 
     * Args:
     *   nums: int[] - 输入的整数数组
     * 
     * Returns:
     *   List<List<Integer>> - 所有可能的子集
     * 
     * Time: O(n * 2^n) - 共有2^n个子集，每个子集需要O(n)时间复制
     * Space: O(n) - 递归栈深度为n，path数组长度为n
     */
    public List<List<Integer>> subsets(int[] nums) {
        this.nums= nums;
        backtrack(0);
        return ans;
    }

    private void backtrack(int i){
        ans.add(new ArrayList<>(path)); // 复制 path
        for(int j = i; j < nums.length; j++){
            path.add(nums[j]); 
            backtrack(j+1);
            path.remove(path.size() - 1); // 恢复现场
        }
    }

    public List<List<Integer>> subsets1(int[] nums) {
        this.nums= nums;
        backtrack1(0);
        return ans;
    }

    private void backtrack1(int i){
        if (i == nums.length){
            ans.add(new ArrayList<>(path));
            return;
        }
        // 不选 nums[i]
        backtrack1(i+1);
        // 选 nums[i]
        path.add(nums[i]); 
        backtrack1(i+1);
        path.remove(path.size() - 1); // 恢复现场
    }
}